#include <iostream>

using namespace std;

typedef long long LL;

int a, m;
string s;

LL get_phi(LL x)
{
	LL ret = x;
	for(int i = 2; i <= x / i; i++)
	{
		if(x % i == 0) 
		{
			ret = ret / i * (i - 1);
			while(x % i == 0) x /= i;
		}
		
	}
	if(x > 1) ret = ret / x * (x - 1);
	return ret;
}

LL get_b(string& s, LL phi)
{
	LL ret = 0;
	bool flag = false;
	for(auto ch : s)
	{
		ret = ret * 10 + ch - '0';
		if(ret >= phi)
		{
			flag = true;
			ret %= phi;
		}
	}
	if(flag) ret += phi;
	return ret;
}

LL qpow(LL a, LL b, LL p)
{
	LL ret = 1;
	while(b)
	{
		if(b & 1) ret = ret * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return ret;
} 

int main()
{
	cin >> a >> m >> s;
//	cin >> m;
	LL phi = get_phi(m);
//	cout << phi << endl;
	LL b = get_b(s, phi);
	cout << qpow(a, b, m) << endl;
	
	return 0;
}
